The present invention relates to an apparatus for dividing the elements of a Galois field, which can effectively serve to decode an error correction code used in an optical DAD (digital audio disk) device using, for example, a CD (compact disk).
Various optical DAD devices have been developed recently. As is well known, in an optical DAD device using a compact disk, cross-interleaved Reed Solomon codes (CIRC) are used as error correction codes. A cross-interleaved Reed Solomon code is obtained by submitting a Reed Solomon code, which is a BCH code and which is generally regarded as the most effective random error correction code hitherto known, to a signal process called "cross-interleaving". The cross-interleaved Reed Solomon code thus obtained can correct even a burst error.
A Reed Solomon code can be decoded in the same way as is a BCH code, thereby performing an error correction.
A Reed Solomon code consisting of k data symbols and (n-k) inspection symbols, i.e., a code consisting of n symbols, is decoded in the following manner. Here, n symbols are the 2.sup.m elements of a finite field called "Galois field GF(2.sup.m)" which represents m binary bits. The generator polynomial g.sub.(x) representing a Reed Solomon code used to correct an error t times is given by the following equation (1) or (2), where .alpha. is the origin element of the Galois field GF (2.sup.m): EQU g.sub.(x) =(x+.alpha.)(x+.alpha..sup.2), . . . (x+.alpha..sup.2t) (1) EQU g.sub.(x) =(x+.alpha..sup.0)(x+.alpha.), . . . (x+.alpha..sup.2t-1) (2)
Let C.sub.(x), R.sub.(x) and E.sub.(x) denote a transmitted code word, a received code word and an error polynomial respectively, then: EQU R.sub.(x) =C.sub.(x) +E.sub.(x) ( 3)
The coefficients contained in polynomial E.sub.(x) are also contained in Galois field GF (2.sup.m). Hence, the error polynomial E.sub.(x) contains only terms which correspond to an error location and the value (i.e., size) of an error.
Let X.sup.j denote an error location, and let Y.sup.j denote the value of the error at location X.sup.j. Error polynomial E.sub.(x) is then given as: ##EQU1## where .SIGMA. is the sum of errors at all error locations.
Here, syndrome S.sub.i is put: EQU S.sub.i =R(.alpha..sup.i) [i=0, 1, . . . 2t-1] (5)
Then, from equation (3): EQU S.sub.1 =C(.alpha..sup.i)+E(.alpha..sup.i).
Both C(x) and g(x) can be divided, leaving no remainder. The following therefore holds true: EQU S.sub.i =E(.alpha..sup.i).
From equation (4) it is evident that syndrome S.sub.i may be expressed as follows: EQU S.sub.i =E(.alpha..sup.i)=.SIGMA.Y.sub.j (.alpha..sup.i).sup.j =.SIGMA.Y.sub.j X.sub.j.sup.i ( 6)
where .alpha..sup.j =X.sub.j and X.sub.j represents the error location for .alpha..sup.j.
Error location polynomial .alpha..sub.(x) is given by: ##EQU2## where e is the number of errors.
.sigma..sub.1 to .sigma..sub.e in equation (7) are related to syndrome S.sub.i as shown below: EQU S.sub.i+e +.sigma..sub.1 S.sub.i+e-1 +. . . .sigma..sub.e-1 S.sub.i+1 +.sigma..sub.e S.sub.i ( 8)
In other words, such a Reed Solomon code as defined above is decoded in the following steps:
(I) Calculate syndrome S.sub.i [equation (5)]. PA1 (II) Obtain coefficients .sigma..sub.1 to .sigma..sub.e contained in error location polynomial .sigma..sub.(x) [equation (8)]. PA1 (III) Find the root X.sub.j of error location polynomial .sigma..sub.(x) [equation (7)]. PA1 (IV) Find error value Y.sub.j [equation (6)], and calculate error polynomial [equation (4)]. PA1 (V) Correct errors [equation (3)].
Now it will be described how to decode, in the above-mentioned steps, a Reed Solomon code consisting of many blocks of data each block containing four inspection symbols. This code is represented by the following polynomial g.sub.(x) : EQU g.sub.(x) =(x+1)(x+.alpha.)(x+.alpha..sup.2)(x+.alpha..sup.3).
In this case, an error can be corrected two times. The Reed Solomon code may be decoded in the following method A or the following method B.